// https://leetcode.cn/problems/divide-two-integers/submissions/

class Solution {
public:
    int divide(int dividend, int divisor) {
        int result = 0;
        bool neg = (dividend ^ divisor) < 0;
        if (divisor == 0) return dividend >= 0? INT_MAX: INT_MIN;
        if (dividend == INT_MIN) {
            if(divisor == -1) return INT_MAX;
            else if(divisor == 1) return INT_MIN;
        }
        // -2147483648 / -1 -> 2147483647
        long long a = llabs(dividend);
        long long b = llabs(divisor);
        while (a >= b) {
            int shift = 0;
            while (a >= (b << shift)) {
                shift++;
            }
            a -= b << (shift - 1);
            result += 1 << (shift - 1);
        }
        return neg? -result: result;
    }
};